#include "../../tools.h"


class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int M = grid.size(), N = grid[0].size();
        vector<vector<int>> dp(M + 1, vector<int>((N + 1), 1<<20));
        dp[M - 1][N - 1] = grid[M - 1][N - 1];
        // show(dp);

        for(int i = M - 1; i > -1; --i){
            for(int j = N - 1; j > -1; --j){
                if(i == M - 1 && j == N - 1) continue;
                dp[i][j] = min(dp[i + 1][j], dp[i][j + 1]) + grid[i][j];
            }
        }

        // show(dp);

        return dp[0][0];
    }
};


int main(int argc, char const *argv[])
{
    vector<vector<int>> grid = {{1,3,1},{1,5,1},{4,2,1}};
    Solution s;
    cout << s.minPathSum(grid);


    return 0;
}
